// ported from eclipse.
var TreeLineTracker = (function (){
    var p;

    function Node(length, delimiter){
        this.length = length;
        this.delimiter = delimiter;
    }
    p = Node.prototype;

    p.line = 0;
    p.length = 0;
    p.offset = 0;
    p.delimiter = '';
    p.parent = null;
    p.left = null;
    p.right = null;
    p.balance = 0;

    p.pureLength = function (){
        return this.length - this.delimiter.length;
    };

    function TreeLineTracker(){
        this._root = new Node(0, '');
    }
    p = TreeLineTracker.prototype;

    p._root = null;
    p._delimiters = ['\r','\n','\r\n'];
    p._delimitersRegex = /\r?\n|\r/g;
    p._delimiterInfo = {
        delimiterIndex: 0,
        delimiterLength: 0,
        delimiter: ''
    };

    p._nodeByOffset = function (offset){
        var remaining = offset;
        var node = this._root;
        while (true) {
            if (remaining < node.offset) {
                node = node.left;
            } else {
                remaining -= node.offset;
                if (remaining < node.length ||
                    remaining === node.length && node.right === null) {
                    break;
                }
                remaining -= node.length;
                node = node.right;
            }
        }
        return node;
    };

    p._lineByOffset = function (offset){
        var remaining = offset;
        var node = this._root;
        var line = 0;
        while (true) {
            if (remaining < node.offset) {
                node = node.left;
            } else {
                remaining -= node.offset;
                line += node.line;
                if (remaining < node.length ||
                    remaining === node.length && node.right === null) {
                    return line;
                }
                remaining -= node.length;
                line ++;
                node = node.right;
            }
        }
    };

    p._nodeByLine = function (line){
        var remaining = line;
        var node = this._root;
        while (true) {
            if (remaining === node.line) {
                break;
            }
            if (remaining < node.line) {
                node = node.left;
            } else {
                remaining -= node.line + 1;
                node = node.right;
            }
        }
        return node;
    };

    p._offsetByLine = function (line){
        var remaining = line;
        var offset = 0;
        var node = this._root;
        while (true) {
            if (remaining === node.line) {
                return offset + node.offset;
            }
            if (remaining < node.line) {
                node = node.left;
            } else {
                remaining -= node.line + 1;
                offset += node.offset + node.length;
                node = node.right;
            }
        }
    };

    p._rotateLeft = function (node){
        var child = node.right;
        var leftChild = node.parent === null || node === node.parent.left;
        this._setChild(node.parent, child, leftChild);
        this._setChild(node, child.left, false);
        this._setChild(child, node, true);
        child.line += node.line + 1;
        child.offset += node.offset + node.length;
    };

    p._rotateRight = function (node){
        var child = node.left;
        var leftChild = node.parent === null || node === node.parent.left;
        this._setChild(node.parent, child, leftChild);
        this._setChild(node, child.right, true);
        this._setChild(child, node, false);
        node.line -= child.line + 1;
        node.offset -= child.offset + child.length;
    };

    p._setChild = function (parent, child, isLeftChild){
        if (parent === null) {
            if (child === null) {
                this._root = new Node(0, '');
            } else {
                this._root = child;
            }
        } else {
            if (isLeftChild) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        if (child !== null) {
            child.parent = parent;
        }
    };

    p._singleLeftRotation = function (node, parent){
        this._rotateLeft(parent);
        node.balance = 0;
        parent.balance = 0;
    };

    p._singleRightRotation = function (node, parent){
        this._rotateRight(parent);
        node.balance = 0;
        parent.balance = 0;
    };

    p._rightLeftRotation = function (node, parent){
        var child = node.left;
        this._rotateRight(node);
        this._rotateLeft(parent);
        if (child.balance === 1) {
            node.balance = 0;
            parent.balance = -1;
            child.balance = 0;
        } else if (child.balance === 0) {
            node.balance = 0;
            parent.balance = 0;
        } else if (child.balance === -1) {
            node.balance = 1;
            parent.balance = 0;
            child.balance = 0;
        }
    };

    p._leftRightRotation = function (node, parent){
        var child = node.right;
        this._rotateLeft(node);
        this._rotateRight(parent);
		if (child.balance === -1) {
			node.balance = 0;
			parent.balance = 1;
			child.balance = 0;
		} else if (child.balance === 0) {
			node.balance = 0;
			parent.balance = 0;
		} else if (child.balance === 1) {
			node.balance = -1;
			parent.balance = 0;
			child.balance = 0;
		}
    };

    p._insertAfter = function (node, length, delimiter){
        var added = new Node(length, delimiter);
        if (node.right === null) {
            this._setChild(node, added, false);
        } else {
            this._setChild(this._successorDown(node.right), added, true);
        }
        this._updateParentChain(added, length, 1);
        this._updateParentBalanceAfterInsertion(added);
        return added;
    };

    p._updateParentBalanceAfterInsertion = function (node){
        var parent = node.parent;
		while (parent !== null) {
			if (node === parent.left) {
				parent.balance --;
            } else {
				parent.balance ++;
            }
			switch (parent.balance) {
				case 1:
				case -1:
					node = parent;
					parent = node.parent;
					continue;
				case -2:
					this._rebalanceAfterInsertionLeft(node);
					break;
				case 2:
					this._rebalanceAfterInsertionRight(node);
					break;
				case 0:
					break;
			}
			return;
		}
    };

    p._rebalanceAfterInsertionRight = function (node){
		var parent= node.parent;
		if (node.balance === 1) {
			this._singleLeftRotation(node, parent);
		} else if (node.balance === -1) {
			this._rightLeftRotation(node, parent);
		}
    };

    p._rebalanceAfterInsertionLeft = function (node){
		var parent= node.parent;
		if (node.balance === -1) {
			this._singleRightRotation(node, parent);
		} else if (node.balance === 1) {
			this._leftRightRotation(node, parent);
		}
    };

    p.replace = function (offset, length, text){
        var remaining = offset;
        var first = this._root;
        var firstNodeOffset;
        while (true) {
			if (remaining < first.offset) {
				first = first.left;
			} else {
				remaining -= first.offset;
				if (remaining < first.length ||
                    remaining === first.length && first.right === null) {
					firstNodeOffset = offset - remaining;
					break;
				}
				remaining -= first.length;
				first = first.right;
			}
        }

        var last;
		if (offset + length < firstNodeOffset + first.length) {
			last = first;
        } else {
			last = this._nodeByOffset(offset + length);
        }

		var firstLineDelta = firstNodeOffset + first.length - offset;
		if (first === last) {
			this._replaceInternal(first, text, length, firstLineDelta);
        } else {
			this._replaceFromTo(first, last, text, length, firstLineDelta);
        }
    };

    p._replaceInternal = function (node, text, length, firstLineDelta){
        var info = text === null ? null : this.$nextDelimiterInfo(text, 0);
        if (info === null || info.delimiter === null) {
            var added = text === null ? 0 : text.length;
            this._updateLength(node, added - length);
        } else {
            var remainder = firstLineDelta - length;
            var remDelim = node.delimiter;
            var consumed = info.delimiterIndex + info.delimiterLength;
            var delta = consumed - firstLineDelta;
            this._updateLength(node, delta);
            node.delimiter = info.delimiter;
            info = this.$nextDelimiterInfo(text, consumed);
            while (info !== null) {
                var lineLen = info.delimiterIndex - consumed + info.delimiterLength;
                node = this._insertAfter(node, lineLen, info.delimiter);
                consumed += lineLen;
                info = this.$nextDelimiterInfo(text, consumed);
            }
            this._insertAfter(node, remainder + text.length - consumed, remDelim);
        }
    };

    p._replaceFromTo = function (node, last, text, length, firstLineDelta){
		var successor= this._successor(node);
		while (successor !== last) {
			length -= successor.length;
			var toDelete = successor;
			successor= this._successor(successor);
			this._updateLength(toDelete, -toDelete.length);
		}

		var info = text === null ? null : this.$nextDelimiterInfo(text, 0);
		if (info === null || info.delimiter === null) {
			var added = text === null ? 0 : text.length;
			this._join(node, last, added - length);
		} else {
			var consumed = info.delimiterIndex + info.delimiterLength;
			this._updateLength(node, consumed - firstLineDelta);
			node.delimiter = info.delimiter;
			length -= firstLineDelta;
			info = this.$nextDelimiterInfo(text, consumed);
			while (info != null) {
				var lineLen = info.delimiterIndex - consumed + info.delimiterLength;
				node = this._insertAfter(node, lineLen, info.delimiter);
				consumed += lineLen;
				info = this.$nextDelimiterInfo(text, consumed);
			}
			this._updateLength(last, text.length - consumed - length);
		}
    };

    p._join = function (one, two, delta){
        var oneLength = one.length;
        this._updateLength(one, -oneLength);
        this._updateLength(two, oneLength + delta);
    };

    p._updateLength = function (node, delta){
        node.length += delta;
        var lineDelta;
        var delete_ = node.length === 0 && node.delimiter !== '';
        if (delete_) {
            lineDelta = -1;
        } else {
            lineDelta = 0;
        }
        if (delta !== 0 || lineDelta !== 0) {
            this._updateParentChain(node, delta, lineDelta);
        }
        if (delete_) {
            this._delete(node);
        }
    };

    p._updateParentChain = function (node, deltaLength, deltaLines){
        this._updateParentChain0(node, null, deltaLength, deltaLines);
    };

    p._updateParentChain0 = function (from, to, deltaLength, deltaLines){
        var parent = from.parent;
        while (parent !== to) {
            if (from === parent.left) {
                parent.offset += deltaLength;
                parent.line += deltaLines;
            }
            from = parent;
            parent = from.parent;
        }
    };

    p._delete = function (node){
        var parent = node.parent;
        var toUpdate;
        var lostLeftChild;
        var isLeftChild = parent === null || node === parent.left;
        var replacement;
        if (node.left === null || node.right === null) {
            replacement = node.left === null ? node.right : node.left;
            this._setChild(parent, replacement, isLeftChild);
            toUpdate = parent;
            lostLeftChild = isLeftChild;
        } else if (node.right.left === null) {
            replacement = node.right;
            this._setChild(parent, replacement, isLeftChild);
            this._setChild(replacement, node.left, true);
            replacement.line = node.line;
            replacement.offset = node.offset;
            replacement.balance = node.balance;
            toUpdate = replacement;
            lostLeftChild = false;
        } else {
            var successor = this._successor(node);
            toUpdate = successor.parent;
            this._updateParentChain0(successor, node, -successor.length, -1);
            this._setChild(toUpdate, successor.right, true);
            this._setChild(successor, node.right, false);
            this._setChild(successor, node.left, true);
            this._setChild(parent, successor, isLeftChild);
            successor.line = node.line;
            successor.offset = node.offset;
            successor.balance = node.balance;
        }
        this._updateParentBalanceAfterInsertion2(toUpdate, lostLeftChild);
    };

    p._updateParentBalanceAfterInsertion2 = function (node, wasLeftChild){
        while (node !== null) {
            if (wasLeftChild) {
                node.balance ++;
            } else {
                node.balance --;
            }
            var parent = node.parent;
            if (parent !== null) {
                wasLeftChild = node === parent.left;
            }
            switch (node.balance) {
				case 1:
				case -1:
					return;
				case -2:
					if (this._rebalanceAfterDeletionRight(node.left)) {
						return;
                    }
					break;
				case 2:
					if (this._rebalanceAfterDeletionLeft(node.right)) {
						return;
                    }
					break;
				case 0:
					break;
            }
            node = parent;
        }
    };

    p._rebalanceAfterDeletionLeft = function (node){
        var parent = node.parent;
		if (node.balance === 1) {
			this._singleLeftRotation(node, parent);
			return false;
		} else if (node.balance === -1) {
			this._rightLeftRotation(node, parent);
			return false;
		} else if (node.balance === 0) {
			this._rotateLeft(parent);
			node.balance = -1;
			parent.balance = 1;
			return true;
		}
    };

    p._rebalanceAfterDeletionRight = function (node){
		var parent= node.parent;
		if (node.balance === -1) {
			this._singleRightRotation(node, parent);
			return false;
		} else if (node.balance === 1) {
			this._leftRightRotation(node, parent);
			return false;
		} else if (node.balance === 0) {
			this._rotateRight(parent);
			node.balance = 1;
			parent.balance = -1;
			return true;
		}
    };

    p._successor = function (node){
        if (node.right !== null) {
            return this._successorDown(node.right);
        }
        return this._successorUp(node);
    };

    p._successorUp = function (node){
        var child = node;
        var parent = child.parent;
        while (parent !== null) {
            if (child === parent.left) {
                return parent;
            }
            child = parent;
            parent = child.parent;
        }
        return null;
    };

    p._successorDown = function (node){
        var child = node.left;
        while (child !== null) {
            node = child;
            child = node.left;
        }
        return node;
    };

    p.$nextDelimiterInfo = function (text, offset){
        var regex = this._delimitersRegex;
        var delimiterInfo = this._delimiterInfo;
        regex.lastIndex = offset;
        var match = regex.exec(text);
        if (match) {
            delimiterInfo.delimiterIndex = match.index;
            delimiterInfo.delimiterLength = match[0].length;
            delimiterInfo.delimiter = match[0];
            return delimiterInfo;
        }
        return null;
    };

    p.getLegalLineDelimiters = function (){
        return this._delimiters.slice(0);
    };

    p.getLineDelimiter = function (line){
        var node = this._nodeByLine(line);
        return node.delimiter === '' ? null : node.delimiter;
    };

    p.computeNumberOfLines = function (text){
		var count= 0;
		var start= 0;
		var delimiterInfo = this.$nextDelimiterInfo(text, start);
		while (delimiterInfo !== null && delimiterInfo.delimiterIndex > -1) {
			++ count;
			start = delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
			delimiterInfo = this.$nextDelimiterInfo(text, start);
		}
		return count;
    };

    p.getNumberOfLines = function (){
        var node = this._root;
        var lines = 0;
		while (node !== null) {
			lines += node.line + 1;
			node = node.right;
		}
		return lines;
    };

    p.getNumberOfLines2 = function (offset, length){
        if (length === 0) {
            return 1;
        }
		var startLine = this._lineByOffset(offset);
		var endLine = this._lineByOffset(offset + length);
		return endLine - startLine + 1;
    };

    p.getLineOffset = function (line){
        return this._offsetByLine(line);
    };

    p.getLineLength = function (line){
        var node = this._nodeByLine(line);
        return node.length;
    };

    p.getLineNumberOfOffset = function (offset){
        return this._lineByOffset(offset);
    };

    p.getLineInfomationOfOffset = function (offset){
		var remaining= offset;
		var node = this._root;
		var lineOffset;
		while (true) {
			if (remaining < node.offset) {
				node = node.left;
			} else {
				remaining -= node.offset;
				if (remaining < node.length ||
                    remaining === node.length && node.right === null) { // last line
					lineOffset = offset - remaining;
					break;
				}
				remaining -= node.length;
				node = node.right;
			}
		}
		return [lineOffset, node.pureLength()];
    };

    p.getLineInformation = function (line){
        var remaining = line;
        var offset = 0;
        var node = this._root;
        while (true) {
            if (remaining === node.line) {
                offset += node.offset;
                break;
            }
            if (remaining < node.line) {
                node = node.left;
            } else {
                remaining -= node.line + 1;
                offset += node.offset + node.length;
                node = node.right;
            }
        }
        return [offset, node.pureLength()];
    };

    p.set = function (text){
        this._root = new Node(0, '');
        this.replace(0, 0, text);
    };

//=============
    p.init$LineTracker = function (){
        this._root = new Node(0, '');
    };
    p.update$LineTracker = function (offset, length, text){
        var startIndex = this._lineByOffset(offset);
        var endIndexOld = this._lineByOffset(offset + length);
        this.replace(offset, length, text);
        var endIndex = this._lineByOffset(offset + text.length);
        return {
            startIndex: startIndex,
            endIndexOld: endIndexOld,
            endIndex: endIndex
        };
    };
    p.update = p.update$LineTracker;
    p.getLineCount = p.getNumberOfLines;
    p.getLineIndex = p.getLineNumberOfOffset;
    p.getLineStartOffset = p.getLineOffset;
    p.getLineEndOffset = function (line){
        var r = this.getLineInformation(line);
        return r[0] + r[1];
    };

    return TreeLineTracker;
})();
